package com.peng.leetcode.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * IsValidSerialization
 *
 * @author: lupeng6
 * @create: 2021/3/12 11:17
 */
public class IsValidSerialization {

    public static void main(String[] args) {
        String s = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        System.out.println(new IsValidSerialization().isValidSerialization(s));
    }

    public boolean isValidSerialization(String preorder) {
        if (preorder.equals("#")) {
            return true;
        }
        int len = preorder.length();
        Deque<Integer> stack = new LinkedList<>();
        stack.push(1);
        int index = 0;

        while (index < len) {
            char c = preorder.charAt(index);
            if (c == ',') {
                index++;
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            Integer top = stack.pop();
            if (Character.isDigit(c)) {
                // 读取一个数字
                while (index < len && preorder.charAt(index) != ',') {
                    index++;
                }
                top--;
                if (top != 0) {
                    stack.push(top);
                }
                stack.push(2);
            } else {
                // c == #
                top--;
                if (top != 0) {
                    stack.push(top);
                }
                index++;
            }
        }
        return stack.isEmpty();
    }
}
